<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Cardinal B-splines</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../sf_poly.html" title="Polynomials">
<link rel="prev" href="sph_harm.html" title="Spherical Harmonics">
<link rel="next" href="gegenbauer.html" title="Gegenbauer Polynomials">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sph_harm.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../sf_poly.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="gegenbauer.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.sf_poly.cardinal_b_splines"></a><a class="link" href="cardinal_b_splines.html" title="Cardinal B-splines">Cardinal B-splines</a>
</h3></div></div></div>
<h5>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h0"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.synopsis"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.synopsis">Synopsis</a>
      </h5>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">cardinal_b_spline</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">&gt;</span>
<span class="keyword">auto</span> <span class="identifier">cardinal_b_spline</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">&gt;</span>
<span class="keyword">auto</span> <span class="identifier">cardinal_b_spline_prime</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">&gt;</span>
<span class="keyword">auto</span> <span class="identifier">cardinal_b_spline_double_prime</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">&gt;</span>
<span class="identifier">Real</span> <span class="identifier">forward_cardinal_b_spline</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>

<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
        Cardinal <span class="emphasis"><em>B</em></span>-splines are a family of compactly supported
        functions useful for the smooth interpolation of tables.
      </p>
<p>
        The first <span class="emphasis"><em>B</em></span>-spline <span class="emphasis"><em>B</em></span><sub>0</sub> is simply
        a box function: It takes the value one inside the interval [-1/2, 1/2], and
        is zero elsewhere. <span class="emphasis"><em>B</em></span>-splines of higher smoothness are
        constructed by iterative convolution, namely, <span class="emphasis"><em>B</em></span><sub>1</sub> :=
        <span class="emphasis"><em>B</em></span><sub>0</sub> ∗ <span class="emphasis"><em>B</em></span><sub>0</sub>, and <span class="emphasis"><em>B</em></span><sub><span class="emphasis"><em>n</em></span>+1</sub> :=
        <span class="emphasis"><em>B</em></span><sub><span class="emphasis"><em>n</em></span> </sub> ∗ <span class="emphasis"><em>B</em></span><sub>0</sub>.
        For example, <span class="emphasis"><em>B</em></span><sub>1</sub>(<span class="emphasis"><em>x</em></span>) = 1 - |<span class="emphasis"><em>x</em></span>|
        for <span class="emphasis"><em>x</em></span> in [-1,1], and zero elsewhere, so it is a hat
        function.
      </p>
<p>
        A basic usage is as follows:
      </p>
<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cardinal_b_spline</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cardinal_b_spline_prime</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cardinal_b_spline_double_prime</span><span class="special">;</span>
<span class="keyword">double</span> <span class="identifier">x</span> <span class="special">=</span> <span class="number">0.5</span><span class="special">;</span>
<span class="comment">// B₀(x), the box function:</span>
<span class="keyword">double</span> <span class="identifier">y</span> <span class="special">=</span> <span class="identifier">cardinal_b_spline</span><span class="special">&lt;</span><span class="number">0</span><span class="special">&gt;(</span><span class="identifier">x</span><span class="special">);</span>
<span class="comment">// B₁(x), the hat function:</span>
<span class="identifier">y</span> <span class="special">=</span> <span class="identifier">cardinal_b_spline</span><span class="special">&lt;</span><span class="number">1</span><span class="special">&gt;(</span><span class="identifier">x</span><span class="special">);</span>
<span class="comment">// First derivative of B₃:</span>
<span class="identifier">yp</span> <span class="special">=</span> <span class="identifier">cardinal_b_spline_prime</span><span class="special">&lt;</span><span class="number">3</span><span class="special">&gt;(</span><span class="identifier">x</span><span class="special">);</span>
<span class="comment">// Second derivative of B₃:</span>
<span class="identifier">ypp</span> <span class="special">=</span> <span class="identifier">cardinal_b_spline_double_prime</span><span class="special">&lt;</span><span class="number">3</span><span class="special">&gt;(</span><span class="identifier">x</span><span class="special">);</span>
</pre>
<p>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/central_b_splines.svg"></object></span> <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/central_b_spline_derivatives.svg"></object></span>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/central_b_spline_second_derivatives.svg"></object></span>
      </p>
<h4>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h1"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.caveats"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.caveats">Caveats</a>
      </h4>
<p>
        Numerous notational conventions for <span class="emphasis"><em>B</em></span>-splines exist.
        Whereas Boost.Math (following Kress) zero indexes the <span class="emphasis"><em>B</em></span>-splines,
        other authors (such as Schoenberg and Massopust) use 1-based indexing. So
        (for example) Boost.Math's hat function <span class="emphasis"><em>B</em></span><sub>1</sub> is what Schoenberg
        calls <span class="emphasis"><em>M</em></span><sub>2</sub>. Mathematica, like Boost, uses the zero-indexing
        convention for its <code class="computeroutput"><span class="identifier">BSplineCurve</span></code>.
      </p>
<p>
        Even the support of the splines is not agreed upon. Mathematica starts the
        support of the splines at zero and rescales the independent variable so that
        the support of every member is [0, 1]. Massopust as well as Unser puts the
        support of the <span class="emphasis"><em>B</em></span>-splines at [0, <span class="emphasis"><em>n</em></span>],
        whereas Kress centers them at zero. Schoenberg distinguishes between the
        two cases, called the splines starting at zero forward splines, and the ones
        symmetric about zero <span class="emphasis"><em>central</em></span>.
      </p>
<p>
        The <span class="emphasis"><em>B</em></span>-splines of Boost.Math are central, with support
        support [-(<span class="emphasis"><em>n</em></span>+1)/2, (<span class="emphasis"><em>n</em></span>+1)/2]. If
        necessary, the forward splines can be evaluated by using <code class="computeroutput"><span class="identifier">forward_cardinal_b_spline</span></code>,
        whose support is [0, <span class="emphasis"><em>n</em></span>+1].
      </p>
<h4>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h2"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.implementation"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.implementation">Implementation</a>
      </h4>
<p>
        The implementation follows Maurice Cox' 1972 paper 'The Numerical Evaluation
        of B-splines', and uses the triangular array of Algorithm 6.1 of the reference
        rather than the rhombohedral array of Algorithm 6.2. Benchmarks revealed
        that the time to calculate the indexes of the rhombohedral array exceed the
        time to simply add zeroes together, except for <span class="emphasis"><em>n</em></span> &gt;
        18. Since few people use <span class="emphasis"><em>B</em></span> splines of degree 18, the
        triangular array is used.
      </p>
<h4>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h3"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.performance"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.performance">Performance</a>
      </h4>
<p>
        Double precision timing on a consumer x86 laptop is shown below:
      </p>
<pre class="programlisting"><span class="identifier">Run</span> <span class="identifier">on</span> <span class="special">(</span><span class="number">16</span> <span class="identifier">X</span> <span class="number">4300</span> <span class="identifier">MHz</span> <span class="identifier">CPU</span> <span class="identifier">s</span><span class="special">)</span>
<span class="identifier">CPU</span> <span class="identifier">Caches</span><span class="special">:</span>
  <span class="identifier">L1</span> <span class="identifier">Data</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
  <span class="identifier">L1</span> <span class="identifier">Instruction</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
  <span class="identifier">L2</span> <span class="identifier">Unified</span> <span class="number">1024</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x8</span><span class="special">)</span>
  <span class="identifier">L3</span> <span class="identifier">Unified</span> <span class="number">11264</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x1</span><span class="special">)</span>
<span class="identifier">Load</span> <span class="identifier">Average</span><span class="special">:</span> <span class="number">0.21</span><span class="special">,</span> <span class="number">0.33</span><span class="special">,</span> <span class="number">0.29</span>
<span class="special">-----------------------------------------</span>
<span class="identifier">Benchmark</span>                            <span class="identifier">Time</span>
<span class="special">-----------------------------------------</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">1</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">18.8</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">2</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">25.3</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">3</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">29.3</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">4</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">33.8</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">5</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">36.7</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">6</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">39.1</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">7</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">43.6</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">8</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">62.8</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">9</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">70.2</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">10</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>       <span class="number">83.8</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">11</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>       <span class="number">94.3</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">12</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">108</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">13</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">122</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">14</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">138</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">15</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">155</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">16</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">170</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">17</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">192</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">18</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">174</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">19</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">180</span> <span class="identifier">ns</span>
<span class="identifier">CardinalBSpline</span><span class="special">&lt;</span><span class="number">20</span><span class="special">,</span> <span class="keyword">double</span><span class="special">&gt;</span>        <span class="number">194</span> <span class="identifier">ns</span>
<span class="identifier">UniformReal</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;</span>               <span class="number">11.5</span> <span class="identifier">ns</span>
</pre>
<p>
        A uniformly distributed random number within the support of the spline is
        generated for the argument, so subtracting 11.5 ns from these gives a good
        idea of the performance of the calls.
      </p>
<h4>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h4"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.accuracy"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.accuracy">Accuracy</a>
      </h4>
<p>
        Some representative ULP plots are shown below. The error grows linearly with
        <span class="emphasis"><em>n</em></span>, as expected from Cox equation 10.5.
      </p>
<p>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/b_spline_ulp_3.svg"></object></span> <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/b_spline_ulp_5.svg"></object></span>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../graphs/b_spline_ulp_9.svg"></object></span>
      </p>
<h4>
<a name="math_toolkit.sf_poly.cardinal_b_splines.h5"></a>
        <span class="phrase"><a name="math_toolkit.sf_poly.cardinal_b_splines.references"></a></span><a class="link" href="cardinal_b_splines.html#math_toolkit.sf_poly.cardinal_b_splines.references">References</a>
      </h4>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            I.J. Schoenberg, <span class="emphasis"><em>Cardinal Spline Interpolation</em></span>,
            SIAM Volume 12, 1973
          </li>
<li class="listitem">
            Rainer Kress, <span class="emphasis"><em>Numerical Analysis</em></span>, Springer, 1998
          </li>
<li class="listitem">
            Peter Massopust, <span class="emphasis"><em>On Some Generalizations of B-splines</em></span>,
            arxiv preprint, 2019
          </li>
<li class="listitem">
            Michael Unser and Thierry Blu, <span class="emphasis"><em>Fractional Splines and Wavelets</em></span>,
            SIAM Review 2000, Volume 42, No. 1
          </li>
<li class="listitem">
            Cox, Maurice G. <span class="emphasis"><em>The numerical evaluation of B-splines.</em></span>,
            IMA Journal of Applied Mathematics 10.2 (1972): 134-149.
          </li>
</ul></div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sph_harm.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../sf_poly.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="gegenbauer.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
